#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include "maze.h"
#include <time.h>
#include <math.h>

using namespace std;


Maze::Maze(int size)
{
    mazeSize = size;
    maze.resize(size*size);

    outblock = size*size-1;
    //初始化各个block
    for (auto i = maze.begin() ; i != maze.end() ; i++)
        *i = SEALED;
    visited = new bool[size*size];
    for (int i = 0 ; i < size*size ; i++)
        visited[i] = false;
    newMaze(size);
}

Maze::Maze(vector<int> mazeVec)
{
    visited = NULL;
    setMaze(mazeVec);
};

Maze::Maze(int *mazeArray, int size)
{
    visited = NULL;
    setMaze(mazeArray, size);
}

void Maze::setMaze(int *mazeArray, int size)
{
    maze.clear();
    maze.resize(size*size);
    delete [] visited;
    visited = new bool[size*size];
    for (int i = 0 ; i < size*size-1 ; i++)
    {
        maze[i] = mazeArray[i];
        visited[i] = false;
    }
    mazeSize = size;
    outblock = size*size-1;
}

void Maze::setMaze(vector<int> mazeVec)
{
    //为了美观，本程序的迷宫都是方形的
    //判断迷宫是否为方形，不是则抛出错误
    unsigned int vsize = mazeVec.size();
    double r = sqrt(vsize);
    //顺便说一下，不用担心浮点数的不精确存储会对这里的操作产生影响
    //只要稍微看看IEEE754就会知道，把一个一定范围内的整形(abs<2^25)直接赋给一个浮点数
    //是可以精确存储的
    if (r != (int)r)
        throw "Not a square";
    maze.clear();
    maze.resize(vsize);
    delete [] visited;
    visited = new bool[vsize];

    for (int i = 0 ; i < vsize ; i++)
    {
        maze[i] = mazeVec[i];
        visited[i] = false;
    }
    mazeSize = (int)sqrt(vsize);
    outblock = vsize-1;
}

int Maze::getSize()
{
    return mazeSize;
}

bool Maze::solve()
{
    int current = 0;
    if (maze[0]&RIGHT && maze[0]&DOWN)
        return false;
    while (current != outblock )
    {
        if (current == 0)
        {
            if (maze[0]&RIGHT && visited[mazeSize])
                return false;
            if (maze[0]&DOWN && visited[1])
                return false;
        }
        visited[current] = true;
        //向四个方向探测，如果可通则
        if (!(maze[current]&RIGHT) && (current%mazeSize != mazeSize-1) && !visited[current+1])
        {
            path.push(current);
            current++;
            continue;
        }
        if (!(maze[current]&DOWN) && (current+mazeSize < mazeSize*mazeSize) && !visited[current+mazeSize])
        {
            path.push(current);
            current += mazeSize;
            continue;
        }
        if (!(maze[current]&LEFT) && (current%mazeSize != 0) && !visited[current-1])
        {
            path.push(current);
            current--;
            continue;
        }
        if (!(maze[current]&UP) && (current-mazeSize>=0) && !visited[current-mazeSize])
        {
            path.push(current);
            current -= mazeSize;
            continue;
        }
        current = path.top();
        path.pop();
    }
    if (current == 0)
    {
        path = stack<int>();
        return false;
    }
    path.push(current);
    return true;
}

vector<int> Maze::getMaze()
{
    vector<int> mazeVector(mazeSize*mazeSize);
    for (int i = 0 ; i < mazeSize*mazeSize ; i++)
        mazeVector[i] = maze[i];
    return mazeVector;
}

vector<int> Maze::getPath()
{
    vector<int> mazePath;
    stack<int> t_path = path;
    while (!t_path.empty())
    {
        mazePath.push_back(t_path.top());
        t_path.pop();
    }
    reverse(mazePath.begin(), mazePath.end());
    return mazePath;
}
//-------------以下是生成迷宫的实现-------------------//
//算法简述: 由mazeBlock生成一颗树，这样每个block都是可达的

//并查集找根
int Maze::root(int n)
{
    while (v[n] != n)
    {
        v[n] = v[v[n]];
        n = v[n];
    }
    return n;
}

void Maze::newMaze(int size)
{
    srand(time(NULL));
    mazeSize = size;
    outblock = size*size-1;
    //存储结点
    v = new int[size*size];

    //使用加权并查集存储每棵树的结点数
    int *sz = new int[size*size];
    for (int i = 0 ; i < size*size ; i++)
        sz[i] = 1;
    maze.resize(size*size);
    //初始化MazeBlock，每个block都是不相通的
    for (int i = 0 ; i < mazeSize*mazeSize ; i++)
    {
        v[i] = i;
        maze[i] = SEALED;
        visited[i] = false;
    }

    //构建边的集合Edges
    for (int i = 0 ; i != mazeSize*mazeSize ; i++)
    {
        //每次对顶点分析，添加顶点右方和下方的边
        if ( i % mazeSize != mazeSize-1 )
        {
            edge e;
            e.first = i;
            e.second = i+1;
            Edges.push_back(e);
        }

        if (i + mazeSize < mazeSize*mazeSize )
        {
            edge e;
            e.first = i;
            e.second = i+mazeSize;
            Edges.push_back(e);
        }

    }

    while (!Edges.empty())
    {
        vector<edge>::iterator i = Edges.begin();
        int offset = rand()%Edges.size();
        i = i + offset;
        int rt1 = root(i->first);
        int rt2 = root(i->second);
        if (rt1 != rt2)
        {
            //两个block不在同一棵树上,
            //小树添加到大树
            if (sz[rt1] < sz[rt2])
            {
                v[rt1] = rt2;
                sz[rt2] += sz[rt1];
            }
            else
            {
                v[rt2] = rt1;
                sz[rt1] += rt2;
            }
            int diff = i->first - i->second;
            if (diff == 1)
            {
                //说明first在second右边,则开放first的左方,second的右方
                maze[i->first] &= SEALED - LEFT;
                maze[i->second] &= SEALED - RIGHT;
            }
            else if (diff == -1)
            {
                //first在second左边
                maze[i->first] &= SEALED - RIGHT;
                maze[i->second] &= SEALED - LEFT;
            }

            if (diff == mazeSize)
            {
                //说明first在second的下方
                maze[i->first] &= SEALED - UP;
                maze[i->second] &= SEALED - DOWN;
            }
            else if (diff == -1*mazeSize)
            {
                //first在second上方
                maze[i->first] &= SEALED - DOWN;
                maze[i->second] &= SEALED - UP;
            }

        }
        //删除这条边
        Edges.erase(i);
    }
    maze[0] &= SEALED - LEFT;
    maze[mazeSize*mazeSize-1] &= SEALED - RIGHT;
    delete [] v;
    delete [] sz;
}


